\chapter{图}

\section{图}

\subsection{图（Graph）}

你的微信中有若干好友，而你的好友又有若干好友。许许多多的用户组成了一个多对多的关系网，这个关系网就是数据结构中的图。\\

再例如使用地图导航功能时，导航会根据你的出发地和目的地规划最佳的地铁换乘路线。许许多多的地铁站组成的交通网络也可以认为是图。\\

图是一种比树更为复杂的数据结构。树的结点之间是一对多的关系，并且存在父与子的层级划分。而图的顶点之间是多对多关系，并且所有顶点都是平等的，无所谓谁是父子。\\

在图中，最基本的单元是顶点（vertex），相当于树中的结点。顶点之间的关联关系被称为边（edge）。图中包含一组顶点和一组边，通常用V表示顶点集合，用E表示边集合。边可以看作是顶点对，即$ (v, w) \in E,\ v, w \in V $。\\

在有些图中，每一条边并不是完全等同的。例如地铁线路，站与站之间的距离都有可能不同。因此图中会涉及边的权重（weight），涉及到权重的图被称为带权图（weighted graph），也称为网络。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (0,0) {A};
			\node (B) at (0,3) {B};
			\node (C) at (2.5,4) {C};
			\node (D) at (2.5,1) {D};
			\node (E) at (2.5,-3) {E};
			\node (F) at (5,3) {F};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=black,very thick}]
			\path [-] (A) edge node {5} (B);
			\path [-] (B) edge node {3} (C);
			\path [-] (A) edge node {4} (D);
			\path [-] (D) edge node {3} (C);
			\path [-] (A) edge node {3} (E);
			\path [-] (D) edge node {3} (E);
			\path [-] (D) edge node {3} (F);
			\path [-] (C) edge node {5} (F);
			\path [-] (E) edge node {8} (F);
		\end{scope}
	\end{tikzpicture}
	\caption{带权图}
\end{figure}

还有一种图，顶点之间的关联并不是完全对称的。拿微信举例，你的好友列表里有我，但我的好友列表里未必有你。\\

这样一来，顶点之间的边就有了方向的区分，这种带有方向的图被称为有向图（directed graph）。有向边可以使用<v, w>表示从v指向w的边。\\

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (0,0) {A};
			\node (B) at (0,3) {B};
			\node (C) at (2.5,4) {C};
			\node (D) at (2.5,1) {D};
			\node (E) at (5,0) {E};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=black,very thick}]
			\path [<->] (A) edge node {5} (B);
			\path [->] (B) edge node {3} (C);
			\path [->] (A) edge node {4} (D);
			\path [<->] (D) edge node {3} (C);
			\path [<->] (A) edge node {3} (E);
			\path [->] (D) edge node {3} (E);
		\end{scope}
	\end{tikzpicture}
	\caption{有向图}
\end{figure}

相应地，在QQ中，只要我把你从好友里删除，你在自己的好友列表里就看不到我了。因此QQ的好友关系可以认为是一个没有方向区分的图，这种图被称为无向图（undirected graph）。

\vspace{0.5cm}

\subsection{图的术语}

图还有一些有关路径的术语：

\begin{itemize}
	\item 度：一个顶点的度是指与该顶点相关联的边的条数。

	\item 入度：对于有向图，入度为以该顶点为终点的边数。

	\item 出度：对于有向图，入度为以该顶点为起点的边数。

	\item 连通：如果从顶点V到W存在一条路径，则称V和W是连通的。

	\item 路径：顶点V到W的路径是一系列顶点$ \{V, v_1, v_2, \dots, v_n, W\} $的集合，其中任意一对相邻的顶点间都有图中的边。

	\item 路径长度：路径中边的个数，如果是带权图（网络），则是所有边的权重和。

	\item 简单路径：顶点V到W之间的路径中所有顶点都不同。

	\item 回路：起点等于终点的路径。
\end{itemize}

\begin{tcolorbox}
	\mybox{握手定理Handshaking Theorem}\\
	假设$ G = (V, E) $是无向图，每条边都会给顶点的度之和增加2，则
	\begin{align}
		\sum_{v \in V} deg(v) = 2|E|
	\end{align}
\end{tcolorbox}

\begin{tcolorbox}
	\mybox{Exercise}
	一个有10个顶点，且每个顶点的度都为6的图，有多少条边？
	\begin{align*}
		2m & = 6 \times 10 \\
		m  & = 30
	\end{align*}
\end{tcolorbox}

\newpage

\section{图的表示}

\subsection{邻接矩阵（Adjacency Matrix）}

拥有n个顶点的图，它所包含的边的数量最多是n(n-1)条，因此，要表达各个顶点之间的关联关系，最清晰易懂的方式是使用邻接矩阵G[N][N]。\\

对于无向图来说，如果顶点之间有关联，那么邻接矩阵中对应的值为1；如果顶点之间没有关联，那么邻接矩阵中对应的值为0。

\vspace{-0.5cm}

\begin{align}\nonumber
	G[i][j] = \begin{cases}
		1 & <v_i, v_j>\text{是G中的边}   \\
		0 & <v_i, v_j>\text{不是G中的边} \\
	\end{cases}
\end{align}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (0,0) {A};
			\node (B) at (0,3) {B};
			\node (C) at (2.5,4) {C};
			\node (D) at (2.5,1) {D};
			\node (E) at (4,2) {E};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={},
			every edge/.style={draw=black,very thick}]
			\path [-] (A) edge node {} (B);
			\path [-] (A) edge node {} (D);
			\path [-] (B) edge node {} (C);
			\path [-] (C) edge node {} (D);
			\path [-] (C) edge node {} (E);
		\end{scope}
	\end{tikzpicture}
\end{figure}

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|c|c|}
			\hline
			           & \textbf{A} & \textbf{B} & \textbf{C} & \textbf{D} & \textbf{E} \\
			\hline
			\textbf{A} & 0          & 1          & 0          & 1          & 0          \\
			\hline
			\textbf{B} & 1          & 0          & 1          & 0          & 0          \\
			\hline
			\textbf{C} & 0          & 1          & 0          & 1          & 1          \\
			\hline
			\textbf{D} & 1          & 0          & 1          & 0          & 0          \\
			\hline
			\textbf{E} & 0          & 0          & 1          & 0          & 0          \\
			\hline
		\end{tabular}
	}
	\caption{无向图邻接矩阵}
\end{table}

需要注意的是，邻接矩阵从左上到右下的一条对角线上的元素值必然是0，因为任何一个顶点与它自身是没有连接的。同时，无向图对应的邻接矩阵是一个对称矩阵，假如A和B有关联，那么B和A也必定有关联。\\

但是对于有向图的邻接矩阵，不一定是一个对称矩阵，假如A可以达到B，从B未必能达到A。\\

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (0,0) {A};
			\node (B) at (0,3) {B};
			\node (C) at (2.5,4) {C};
			\node (D) at (2.5,1) {D};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={},
			every edge/.style={draw=black,very thick}]
			\path [->] (A) edge node {} (B);
			\path [->] (A) edge node {} (C);
			\path [<->] (C) edge node {} (D);
			\path [->] (D) edge node {} (B);
		\end{scope}
	\end{tikzpicture}
\end{figure}

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|c|}
			\hline
			           & \textbf{A} & \textbf{B} & \textbf{C} & \textbf{D} \\
			\hline
			\textbf{A} & 0          & 1          & 1          & 0          \\
			\hline
			\textbf{B} & 0          & 0          & 0          & 0          \\
			\hline
			\textbf{C} & 0          & 0          & 0          & 1          \\
			\hline
			\textbf{D} & 0          & 1          & 1          & 0          \\
			\hline
		\end{tabular}
	}
	\caption{有向图邻接矩阵}
\end{table}

对于网络，只要把邻接矩阵对应位置的值定义为边$ <v_i, v_j> $的权重即可。\\

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (0,0) {A};
			\node (B) at (3,0) {B};
			\node (C) at (5,2.5) {C};
			\node (D) at (1.5,5) {D};
			\node (E) at (-2,2.5) {E};
			\node (F) at (1.5,2.5) {F};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=black,very thick}]
			\path [->] (A) edge node {5} (B);
			\path [->] (A) edge node {2} (F);
			\path [->] (B) edge node {4} (C);
			\path [->] (C) edge node {9} (D);
			\path [->] (D) edge node {7} (E);
			\path [->] (D) edge node {3} (F);
			\path [->] (E) edge node {1} (A);
			\path [->] (F) edge node {1} (C);
			\path [->] (F) edge node {8} (E);
		\end{scope}
	\end{tikzpicture}
\end{figure}

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|}
			\hline
			           & \textbf{A} & \textbf{B} & \textbf{C} & \textbf{D} & \textbf{E} & \textbf{F} \\
			\hline
			\textbf{A} & $ \infty $ & 5          & $ \infty $ & $ \infty $ & $ \infty $ & 2          \\
			\hline
			\textbf{B} & $ \infty $ & $ \infty $ & 4          & $ \infty $ & $ \infty $ & $ \infty $ \\
			\hline
			\textbf{C} & $ \infty $ & $ \infty $ & $ \infty $ & 9          & $ \infty $ & $ \infty $ \\
			\hline
			\textbf{D} & $ \infty $ & $ \infty $ & $ \infty $ & $ \infty $ & 7          & 3          \\
			\hline
			\textbf{E} & 1          & $ \infty $ & $ \infty $ & $ \infty $ & $ \infty $ & $ \infty $ \\
			\hline
			\textbf{F} & $ \infty $ & $ \infty $ & 1          & $ \infty $ & 8          & $ \infty $ \\
			\hline
		\end{tabular}
	}
	\caption{带权图邻接矩阵}
\end{table}

对于带权图，如果$ v_i $和$ v_j $之前没有边应该将权值设为$ \infty $。\\

邻接矩阵的优点：

\begin{enumerate}
	\item 简单、直观。
	\item 可以快速查到一个顶点和另一顶点之间的关联关系。
	\item 方便计算任一顶点的度，对于有向图，从顶点发出的边数为出度，指向顶点的边数为入度。
\end{enumerate}

邻接矩阵的缺点：

\begin{enumerate}
	\item 浪费空间，对于稀疏图（点很多而边很少）有大量无效元素。但对于稠密图（特别是完全图）还是很合算的。
	\item 浪费时间，统计稀疏图中边的个数，也就是计算邻接矩阵中元素1的个数。
\end{enumerate}

\vspace{0.5cm}

\subsection{邻接表（Adjacency List）}

为了解决邻接矩阵占用空间的问题，人们想到了另一种图的表示方法——邻接表。在邻接表中，图的每一个顶点都是一个链表的头结点，其后连接着该顶点能够直接到达的相邻顶点。对于稀疏图而言，邻接表存储方式占用的空间比邻接矩阵要小得多。\\

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (0,0) {A};
			\node (B) at (0,3) {B};
			\node (C) at (2.5,4) {C};
			\node (D) at (2.5,1) {D};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={},
			every edge/.style={draw=black,very thick}]
			\path [->] (A) edge node {} (B);
			\path [->] (A) edge node {} (C);
			\path [<->] (C) edge node {} (D);
			\path [->] (D) edge node {} (A);
		\end{scope}
	\end{tikzpicture}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\coordinate (0);
		\foreach \t[count=\i from 0,evaluate=\i as\j using int(\i+1)] in {
				1 $ \rightarrow $ 2,
				,
				3,
				1 $ \rightarrow $ 2
			}
		\node at(\i.south)[anchor=north,draw,minimum height=2em,minimum width=1.5em,outer sep=0pt](\j){}
		node at(\j.west)[align=right,left]{\i}
		node at(\j.east)[align=left,right,xshift=-.7em]{$ \rightarrow $ \t};
	\end{tikzpicture}
	\caption{邻接表}
\end{figure}

通过遍历邻接表可以查找到所有能够到达的相邻顶点，但是对于逆向查找，即哪些顶点可以达到一个顶点就会很麻烦。\\

逆邻接表和邻接表是正好相反的，逆邻接表每一个顶点作为链表的头结点，后继结点所存储的是能够直接到达该顶点的相邻顶点。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\coordinate (0);
		\foreach \t[count=\i from 0,evaluate=\i as\j using int(\i+1)] in {
				,
				0 $ \rightarrow $ 3,
				0 $ \rightarrow $ 3,
				2
			}
		\node at(\i.south)[anchor=north,draw,minimum height=2em,minimum width=1.5em,outer sep=0pt](\j){}
		node at(\j.west)[align=right,left]{\i}
		node at(\j.east)[align=left,right,xshift=-.7em]{$ \rightarrow $ \t};
	\end{tikzpicture}
	\caption{逆邻接表}
\end{figure}

可是，一个图要维护正反两个邻接表，也太麻烦了吧？\\

通过十字链表可以把邻接表和逆邻接表结合在一起。\\

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\coordinate (0);
		\foreach \t[count=\i from 0,evaluate=\i as\j using int(\i+1)] in {
				1 $ \rightarrow $ 2,
				,
				3,
				1 $ \rightarrow $ 2
			}
		\node at(\i.south)[anchor=north,draw,minimum height=2em,minimum width=1.5em,outer sep=0pt](\j){}
		node at(\j.east)[align=right,left]{\i}
		node at(\j.east)[align=left,right,xshift=-.7em]{$ \rightarrow $ \t};

		\draw (-0.4,-0.5) node{$ \leftarrow $};
		\draw (-1,-1.2) node{$ 3 \leftarrow 0 \leftarrow $};
		\draw (-1,-2) node{$ 3 \leftarrow 0 \leftarrow $};
		\draw (-0.5,-2.9) node{$ 2 \leftarrow $};
	\end{tikzpicture}
	\caption{十字链表}
\end{figure}

\newpage

\section{特殊图}

\subsection{完全图（Complete Graph）}

完全图是指每对顶点之间都有一条边的简单图，包含n个顶点的完全图记作$ K_n $。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\draw[thick,black]  (18:2) \foreach \a in {90,162,234,306} { -- (\a:2) } -- cycle;
		\draw[thick,black] (18:2) \foreach \a in {162,306,90,234} { -- (\a:2) } -- cycle;
		\foreach \a in {18,90,162,234,306} { \node[black,fill=black,circle,inner sep=2pt] at (\a:2){}; }
	\end{tikzpicture}
	\caption{完全图}
\end{figure}

\vspace{0.5cm}

\subsection{圈图（Cycle Graph）}

圈图是由$ n\ (n \ge 3) $的顶点，及边$ (v_1, v_2) $、$ (v_2, v_3) $、$ (v_{n-1}, v_n) $、$ (v_n, v_1) $组成的简单图。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\draw[thick,black]  (18:2) \foreach \a in {90,162,234,306} { -- (\a:2) } -- cycle;
		\foreach \a in {18,90,162,234,306} { \node[black,fill=black,circle,inner sep=2pt] at (\a:2){}; }
	\end{tikzpicture}
	\caption{圈图}
\end{figure}

\vspace{0.5cm}

\subsection{n立方图}

n立方图记作$ Q_n $，是用顶点表示$ 2^n $个长度为n的二进制串的图。n立方图的两个顶点相邻，当且仅当它们所表示的二进制串恰有一位不同。\\

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\node[draw, black, fill=black, circle, inner sep=2pt, label=above:0] at (0,0){};
		\node[draw, black, fill=black, circle, inner sep=2pt, label=above:1] at (2,0){};
		\draw[black, thick] (0,0) -- (2,0);
	\end{tikzpicture}
	\caption{$ Q_1 $}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\node[black, fill=black, circle, inner sep=2pt, label=left:00] at (0,0){};
		\node[black, fill=black, circle, inner sep=2pt, label=right:01] at (2,0){};
		\node[black, fill=black, circle, inner sep=2pt, label=right:11] at (2,2){};
		\node[black, fill=black, circle, inner sep=2pt, label=left:10] at (0,2){};
		\draw[black, thick] (0,0) -- (2,0) -- (2,2) -- (0,2) -- (0,0);
	\end{tikzpicture}
	\caption{$ Q_2 $}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\node[black, fill=black, circle, inner sep=2pt, label=left:000] at (0,0){};
		\node[black, fill=black, circle, inner sep=2pt, label=right:100] at (2,0){};
		\node[black, fill=black, circle, inner sep=2pt, label=right:110] at (2,2){};
		\node[black, fill=black, circle, inner sep=2pt, label=left:010] at (0,2){};
		\draw[black, thick] (0,0) -- (2,0) -- (2,2) -- (0,2) -- (0,0);

		\node[black, fill=black, circle, inner sep=2pt, label=left:001] at (0.8,0.8){};
		\node[black, fill=black, circle, inner sep=2pt, label=right:101] at (2.8,0.8){};
		\node[black, fill=black, circle, inner sep=2pt, label=right:111] at (2.8,2.8){};
		\node[black, fill=black, circle, inner sep=2pt, label=left:011] at (0.8,2.8){};
		\draw[black, thick] (0.8,0.8) -- (2.8,0.8) -- (2.8,2.8) -- (0.8,2.8) -- (0.8,0.8);

		\draw[black, thick] (0,0) -- (0.8,0.8);
		\draw[black, thick] (0,2) -- (0.8,2.8);
		\draw[black, thick] (2,2) -- (2.8,2.8);
		\draw[black, thick] (2,0) -- (2.8,0.8);
	\end{tikzpicture}
	\caption{$ Q_3 $}
\end{figure}

\vspace{0.5cm}

\subsection{二分图（Bipartite Graph）}

二分图是指图的顶点可以分成两个不相交的子集，使得每条边都连接一个子集中的顶点与另一个子集中的顶点。\\

如果能够对图中的顶点赋予两种不同的颜色，并且使得没有两个相邻的顶点的颜色是一样的，那么这个图是一个二分图。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\node[red, fill=red, circle, inner sep=2pt] at (0,0){};
		\node[black, fill=black, circle, inner sep=2pt] at (2,0){};
		\node[black, fill=black, circle, inner sep=2pt] at (0,2){};
		\node[black, fill=black, circle, inner sep=2pt] at (2,2){};
		\node[red, fill=red, circle, inner sep=2pt] at (1,3){};
		\node[black, fill=black, circle, inner sep=2pt] at (3,3){};
		\node[red, fill=red, circle, inner sep=2pt] at (3,1){};
		\draw[black, thick] (2,0) -- (0,0) -- (0,2) -- (1,3) -- (3,3) -- (3,1) -- (0,2);
		\draw[black, thick] (0,0) -- (2,2) -- (1,3);
	\end{tikzpicture}
	\caption{二分图}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\node[black, fill=black, circle, inner sep=2pt] at (0,0){};
		\node[red, fill=red, circle, inner sep=2pt] at (2,1.5){};
		\node[red, fill=red, circle, inner sep=2pt] at (2,-1.5){};
		\node[black, fill=black, circle, inner sep=2pt] at (4,1.5){};
		\node[black, fill=black, circle, inner sep=2pt] at (4,-1.5){};
		\node[red, fill=red, circle, inner sep=2pt] at (6,0){};
		\draw[black, thick] (0,0) -- (2,1.5) -- (4,1.5) -- (6,0) -- (4,-1.5) -- (2,-1.5) -- (0,0);
	\end{tikzpicture}
	\caption{二分图}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\node[red, fill=red, circle, inner sep=2pt] at (0,1.5){};
		\node[red, fill=red, circle, inner sep=2pt] at (0,3){};
		\node[red, fill=red, circle, inner sep=2pt] at (0,4.5){};
		\node[black, fill=black, circle, inner sep=2pt] at (2,0){};
		\node[black, fill=black, circle, inner sep=2pt] at (2,1.5){};
		\node[black, fill=black, circle, inner sep=2pt] at (2,3){};
		\node[black, fill=black, circle, inner sep=2pt] at (2,4.5){};
		\draw[black, thick] (0,1.5) -- (2,0);
		\draw[black, thick] (0,1.5) -- (2,3);
		\draw[black, thick] (0,1.5) -- (2,4.5);
		\draw[black, thick] (0,3) -- (2,0);
		\draw[black, thick] (0,3) -- (2,4.5);
		\draw[black, thick] (0,4.5) -- (2,1.5);
		\draw[black, thick] (0,4.5) -- (2,3);
		\draw[black, thick] (0,4.5) -- (2,4.5);
	\end{tikzpicture}
	\caption{二分图}
\end{figure}

其中第一和第三个图是同构的，但是第三个图可以更加明显地看出是二分图。\\

如果一个图中存在经过奇数个顶点的环路，那么这个图一定不是二分图。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\draw[thick,black]  (18:2) \foreach \a in {90,162,234,306} { -- (\a:2) } -- cycle;
		\foreach \a in {18,90,162,234,306} { \node[black,fill=black,circle,inner sep=2pt] at (\a:2){}; }
	\end{tikzpicture}
	\caption{非二分图}
\end{figure}

\vspace{0.5cm}

\subsection{同构（Isomorphsim）}

对于同一个图，可以画成各种不同的样子，但都具有相同数目的边、相同数目的顶点，它们有着一一对应的关系，对应的顶点具有相同的连接性。这些图的不同形式称之为图的同构。\\

假设$ G_1 = (V1_1, E_1) $和$ G_2 = (V_2, E_2) $是简单图，若存在从$ V_1 $到$ V_2 $的一一对应函数$ f $，且对于所有$ (u, v) \in E_1 $，都满足$ (f(u), f(v)) \in E_2 $，则称$ G_1 $和$ G_2 $是同构的。

\begin{tcolorbox}
	\mybox{Exercise}
	\begin{figure}[H]
		\centering
		\begin{tikzpicture}
			\node[black, fill=black, circle, inner sep=2pt, label=left:c] at (0,0){};
			\node[black, fill=black, circle, inner sep=2pt, label=right:d] at (2,0){};
			\node[black, fill=black, circle, inner sep=2pt, label=right:b] at (2,2){};
			\node[black, fill=black, circle, inner sep=2pt, label=left:a] at (0,2){};
			\draw[black, thick] (0,0) -- (2,2) -- (2,0) -- (0,2) -- (0,0);
		\end{tikzpicture}

		\begin{tikzpicture}
			\node[black, fill=black, circle, inner sep=2pt, label=left:y] at (1,0){};
			\node[black, fill=black, circle, inner sep=2pt, label=right:x] at (2,1){};
			\node[black, fill=black, circle, inner sep=2pt, label=right:w] at (1,2){};
			\node[black, fill=black, circle, inner sep=2pt, label=left:z] at (0,1){};
			\draw[black, thick] (1,0) -- (2,1) -- (1,2) -- (0,1) -- (1,0);
		\end{tikzpicture}
	\end{figure}

	\vspace{-1cm}

	\begin{align*}
		f(a)         & = w      \\
		f(b)         & = y      \\
		f(c)         & = z      \\
		f(d)         & = x      \\
		(f(a), f(d)) & = (w, x)
	\end{align*}
\end{tcolorbox}

\newpage

\section{图的遍历}

\subsection{深度优先搜索（DFS, Depth First Search）}

深度优先搜索是一种一头扎到底的遍历方法，选择一条路，尽可能不断地深入，遇到死路就回退，回退过程中如果遇到没探索的支路，就进入该支路继续深入。\\

例如一个小镇的每个地点都藏有可以实现愿望的光玉，现在要从0号出生点出发去收集所有的光玉。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (0) at (2.5,4) {0};
			\node (1) at (5,3) {1};
			\node (2) at (2.5,2) {2};
			\node (3) at (1,0) {3};
			\node (4) at (3,0) {4};
			\node (5) at (5,1) {5};
			\node (6) at (6,-1) {6};
			\node (7) at (0,3) {7};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={},
			every edge/.style={draw=black,very thick}]
			\path [-] (0) edge node {} (1);
			\path [-] (0) edge node {} (2);
			\path [-] (0) edge node {} (7);
			\path [-] (1) edge node {} (4);
			\path [-] (1) edge node {} (5);
			\path [-] (2) edge node {} (4);
			\path [-] (3) edge node {} (4);
			\path [-] (5) edge node {} (6);
		\end{scope}
	\end{tikzpicture}
	\caption{深度优先搜索}
\end{figure}

二叉树的先序遍历本质上也可以认为是图的深度优先遍历。要想实现回溯，可以利用栈的先进后出的特性，也可以采用递归的方式，因为递归本身就是基于方法调用栈来实现的。

\vspace{0.5cm}

\subsection{广度优先搜索（BFS, Breath First Search）}

除了深度优先搜索一头扎到底的方法以外，还有一种方法就是首先把从源点相邻的顶点遍历，然后再遍历稍微远一点的顶点，再去遍历更远一点的顶点。\\

二叉树的层次遍历本质上也可以认为是图的广度优先遍历，需要借助队列来实现重放。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}[
			level distance=1.5cm,
			level 1/.style={sibling distance=4cm},
			level 2/.style={sibling distance=2cm},
			level 3/.style={sibling distance=1cm}
		]
		\node[circle,draw] {1}
		child {
				node[circle,draw] {2}
				child {
						node[circle,draw] {4}
						child {node[circle,draw] {8}}
						child {node[circle,draw] {9}}
					}
				child {
						node[circle,draw] {5}
						child {node[circle,draw] {10}}
						child {node[circle,draw] {11}}
					}
			}
		child {
				node[circle,draw] {3}
				child {
						node[circle,draw] {6}
						child {node[circle,draw] {12}}
						child {node[circle,draw] {13}}
					}
				child {
						node[circle,draw] {7}
						child {node[circle,draw] {14}}
						child {node[circle,draw] {15}}
					}
			};
	\end{tikzpicture}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (1) at (0,0) {1};
			\node (2) at (-1,1) {2};
			\node (3) at (1,1) {3};
			\node (4) at (1.5,0) {4};
			\node (5) at (1,-1) {5};
			\node (6) at (-1,-1) {6};
			\node (7) at (-1.5,0) {7};
			\node (8) at (-2,2) {8};
			\node (9) at (-0.5,2) {9};
			\node (10) at (2,2) {10};
			\node (11) at (2.5,1) {11};
			\node (12) at (3,0) {12};
			\node (13) at (2.5,-1) {13};
			\node (14) at (2,-2) {14};
			\node (15) at (0,-2) {15};
			\node (16) at (-2,-2) {16};
			\node (17) at (-2.5,-1) {17};
			\node (18) at (-3,0) {18};
			\node (19) at (-2.5,1) {19};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={},
			every edge/.style={draw=black,very thick}]
			\path [-] (1) edge node {} (2);
			\path [-] (1) edge node {} (3);
			\path [-] (1) edge node {} (4);
			\path [-] (1) edge node {} (5);
			\path [-] (1) edge node {} (6);
			\path [-] (1) edge node {} (7);
			\path [-] (2) edge node {} (8);
			\path [-] (2) edge node {} (9);
			\path [-] (3) edge node {} (10);
			\path [-] (4) edge node {} (11);
			\path [-] (4) edge node {} (12);
			\path [-] (4) edge node {} (13);
			\path [-] (5) edge node {} (14);
			\path [-] (5) edge node {} (15);
			\path [-] (6) edge node {} (16);
			\path [-] (7) edge node {} (17);
			\path [-] (7) edge node {} (18);
			\path [-] (7) edge node {} (19);
		\end{scope}
	\end{tikzpicture}
	\caption{广度优先搜索}
\end{figure}

\newpage

\section{连通图}

\subsection{连通图}

图还有一些有关路径的术语：

\begin{itemize}
	\item 连通：如果从顶点V到W存在一条路径，则称V和W是连通的。

	\item 路径：顶点V到W的路径是一系列顶点$ \{V, v_1, v_2, \dots, v_n, W\} $的集合，其中任意一对相邻的顶点间都有图中的边。

	\item 路径长度：路径中边的个数，如果是带权图（网络），则是所有边的权重和。

	\item 简单路径：顶点V到W之间的路径中所有顶点都不同。

	\item 回路：起点等于终点的路径。
\end{itemize}

如果图中任意两顶点均连通，那么称这个图是一个连通图。\\

一个图的连通分量指的是图的极大连通子图，极大连通子图需要满足两点要求：

\begin{enumerate}
	\item 顶点数到达极大，即再加一个顶点就不连通了。
	\item 边数达到极大，即包含子图中所有顶点相连的所有边。
\end{enumerate}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (0,2) {A};
			\node (B) at (-2,0) {B};
			\node (C) at (0,-2) {C};
			\node (D) at (2,0) {D};
			\node (E) at (-0.75,0) {E};
			\node (F) at (0.75,0) {F};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={},
			every edge/.style={draw=black,very thick}]
			\path [-] (A) edge node {} (B);
			\path [-] (B) edge node {} (C);
			\path [-] (C) edge node {} (D);
			\path [-] (D) edge node {} (A);
			\path [-] (E) edge node {} (F);
		\end{scope}
	\end{tikzpicture}
	\caption{图G}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (0,2) {A};
			\node (B) at (-2,0) {B};
			\node (C) at (0,-2) {C};
			\node (D) at (2,0) {D};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={},
			every edge/.style={draw=black,very thick}]
			\path [-] (A) edge node {} (B);
			\path [-] (B) edge node {} (C);
			\path [-] (C) edge node {} (D);
			\path [-] (D) edge node {} (A);
		\end{scope}
	\end{tikzpicture}
	\caption{是图G的极大连通子图}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (E) at (-0.75,0) {E};
			\node (F) at (0.75,0) {F};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={},
			every edge/.style={draw=black,very thick}]
			\path [-] (E) edge node {} (F);
		\end{scope}
	\end{tikzpicture}
	\caption{是图G的极大连通子图}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (0,2) {A};
			\node (B) at (-2,0) {B};
			\node (C) at (0,-2) {C};
			\node (D) at (2,0) {D};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={},
			every edge/.style={draw=black,very thick}]
			\path [-] (A) edge node {} (B);
			\path [-] (C) edge node {} (D);
			\path [-] (D) edge node {} (A);
		\end{scope}
	\end{tikzpicture}
	\caption{不是图G的极大连通子图}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (B) at (-2,0) {B};
			\node (C) at (0,-2) {C};
			\node (D) at (2,0) {D};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={},
			every edge/.style={draw=black,very thick}]
			\path [-] (B) edge node {} (C);
			\path [-] (C) edge node {} (D);
		\end{scope}
	\end{tikzpicture}
	\caption{不是图G的极大连通子图}
\end{figure}

对于有向图而言，如果有向图中任意一对顶点V和W之间存在双向路径，既可以从$ V $走到$ W $，也可以从$ W $走到$ V $，但这两条路径不一定是同一条，则称该图为强连通图。\\

如果有向图不是强连通图，但将所有的有向边替换为无向边之后可以变为连通图，则称该图为弱连通图。\\

有向图的极大强连通子图称为强连通分量。\\

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (0,2) {A};
			\node (B) at (-2,0) {B};
			\node (C) at (0,-2) {C};
			\node (D) at (2,0) {D};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={},
			every edge/.style={draw=black,very thick}]
			\path [->] (A) edge node {} (B);
			\path [->] (B) edge node {} (C);
			\path [->] (C) edge node {} (A);
			\path [->] (A) edge node {} (D);
		\end{scope}
	\end{tikzpicture}
	\caption{有向图G}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (0,2) {A};
			\node (B) at (-2,0) {B};
			\node (C) at (0,-2) {C};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={},
			every edge/.style={draw=black,very thick}]
			\path [->] (A) edge node {} (B);
			\path [->] (B) edge node {} (C);
			\path [->] (C) edge node {} (A);
		\end{scope}
	\end{tikzpicture}
	\caption{是有向图G的强连通分量}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (D) at (2,0) {D};
		\end{scope}
	\end{tikzpicture}
	\caption{是有向图G的强连通分量}
\end{figure}

\newpage

\section{最短路径}

\subsection{最短路径（Shortest Path）}

在现实中很多需要都运用到了最短路径的算法，例如从一个地铁站到另一个地铁站的最快换乘路线等。地铁线路图中，地铁站可以看作是图的顶点，站与站之间的线路可以看作是边，权重可以是距离、时间、费用等。\\

\begin{figure}[H]
	\centering
	\includegraphics[scale=0.3]{img/Chapter8/8-6/1.png}
	\caption{上海地铁线路图}
\end{figure}

在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径，这条路径就是两点之间的最短路径。其中最短路径的第一个顶点称为源点（source），最后一个顶点为终点（destination）。\\

图的最短路径问题分为2种类型：

\begin{enumerate}
	\item 单源最短路径：从某固定源点出发，求到所有其它顶点的最短路径。
	\item 多源最短路径：求任意两顶点间的最短路径。
\end{enumerate}

\vspace{0.5cm}

\subsection{无权图的单源最短路径算法（SSSP, Single-Source Shortest Path）}

无权图的单源最短路径算法可以按照递增（非递减）的顺序找出到各个顶点的最短路，算法类似广度优先遍历。\\

例如在一个无权图中，以顶点3作为源点，离源点距离为1的顶点有1和6，距离为2的顶点有2和4，距离为3的顶点有5和7。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (1) at (-1.5,2) {1};
			\node (2) at (1.5,2) {2};
			\node (3) at (-4,0) {3};
			\node (4) at (0,0) {4};
			\node (5) at (4,0) {5};
			\node (6) at (-1.5,-2) {6};
			\node (7) at (1.5,-2) {7};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={},
			every edge/.style={draw=black,very thick}]
			\path [->] (1) edge node {} (2);
			\path [->] (1) edge node {} (4);
			\path [->] (2) edge node {} (4);
			\path [->] (2) edge node {} (5);
			\path [->] (3) edge node {} (1);
			\path [->] (3) edge node {} (6);
			\path [->] (4) edge node {} (3);
			\path [->] (4) edge node {} (5);
			\path [->] (4) edge node {} (6);
			\path [->] (4) edge node {} (7);
			\path [->] (5) edge node {} (7);
			\path [->] (7) edge node {} (6);
		\end{scope}
	\end{tikzpicture}
\end{figure}

无权图的单元最短路径算法中，dist[v]存储从源点S到v的最短路径，初始化源点dist[S]的距离为0，path[v]表示达到顶点路径v上一个经过的顶点。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{顶点} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} \\
			\hline
			\textbf{dist} & 1          & 2          & 0          & 2          & 3          & 1          & 3          \\
			\hline
			\textbf{path} & 3          & 1          & -1         & 1          & 2          & 3          & 4          \\
			\hline
		\end{tabular}
	}
	\caption{最短路径表}
\end{table}

\vspace{0.5cm}

\subsection{有权图的单源最短路径算法}

有权图的最短路径不一定是经过顶点树最少的路。如果图中存在负值圈（negative-cost cycle）的话会导致算法失效，因为沿着回路走无穷多次，花销是负无穷。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (1) at (-1.5,2) {1};
			\node (2) at (1.5,2) {2};
			\node (3) at (-4,0) {3};
			\node (4) at (0,0) {4};
			\node (5) at (4,0) {5};
			\node (6) at (-1.5,-2) {6};
			\node (7) at (1.5,-2) {7};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=black,very thick}]
			\path [->] (1) edge node {2} (2);
			\path [->] (1) edge node {1} (4);
			\path [->, red] (4) edge node {3} (2);
			\path [->, red] (2) edge node {-10} (5);
			\path [->] (3) edge node {4} (1);
			\path [->] (3) edge node {5} (6);
			\path [->] (4) edge node {2} (3);
			\path [->, red] (5) edge node {2} (4);
			\path [->] (4) edge node {8} (6);
			\path [->] (4) edge node {4} (7);
			\path [->] (5) edge node {6} (7);
			\path [->] (7) edge node {1} (6);
		\end{scope}
	\end{tikzpicture}
	\caption{负值圈}
\end{figure}

带权图的单源最短路径可以通过迪杰斯特拉（Dijkstra）算法解决。\\

特斯拉？什么鬼？\\

迪杰斯特拉算法的本质是不断刷新起点与其他各个顶点之间的距离表。Dijkstra算法采用了贪心的思想，每次都未收录的顶点中选取dist值最小的收录。每当收录一个顶点时，可能会影响另外一个顶点的dist值。

\vspace{-0.5cm}

$$
	dist[w] = min\{dist[w], dist[v] + weight_{<v, w>}\}
$$

例如计算从源点A到其它各顶点的最短路径。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (-3,2.5) {A};
			\node (B) at (-4,0) {B};
			\node (C) at (0,3) {C};
			\node (D) at (0,0) {D};
			\node (E) at (-1.5,-2.5) {E};
			\node (F) at (2,-1) {F};
			\node (G) at (3,-3) {G};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=black,very thick}]
			\path [-] (A) edge node {5} (B);
			\path [-] (A) edge node {2} (C);
			\path [-] (B) edge node {1} (D);
			\path [-] (B) edge node {6} (E);
			\path [-] (C) edge node {6} (D);
			\path [-] (C) edge node {8} (F);
			\path [-] (E) edge node {1} (D);
			\path [-] (E) edge node {7} (G);
			\path [-] (F) edge node {3} (G);
		\end{scope}
	\end{tikzpicture}
\end{figure}

第1步：创建距离表。其中表中key是顶点名称，value是源点A到对应顶点的已知最短距离。一开始并不知道最短路径是多少，因此value都为$ \infty $。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|c|c|}
			\hline
			\textbf{B} & \textbf{C} & \textbf{D} & \textbf{E} & \textbf{F} & \textbf{G} \\
			\hline
			$ \infty $ & $ \infty $ & $ \infty $ & $ \infty $ & $ \infty $ & $ \infty $ \\
			\hline
		\end{tabular}
	}
\end{table}

第2步：找到源点A的邻接点B和C，从A到B的距离是5，从A到C的距离是2。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|c|c|}
			\hline
			\textbf{B}         & \textbf{C}         & \textbf{D} & \textbf{E} & \textbf{F} & \textbf{G} \\
			\hline
			\textcolor{red}{5} & \textcolor{red}{2} & $ \infty $ & $ \infty $ & $ \infty $ & $ \infty $ \\
			\hline
		\end{tabular}
	}
\end{table}

第3步：从距离表中找到从A出发距离最短的顶点，也就是顶点C。找到顶点C的邻接点D和F（A已经遍历过不需要考虑）。从C到D的距离是6，所以从A到D的距离是2 + 6 = 8；从C到F的距离是8，所以从A到F的距离是2 + 8 = 10。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|c|c|}
			\hline
			\textbf{B} & \textbf{C} & \textbf{D}         & \textbf{E} & \textbf{F}          & \textbf{G} \\
			\hline
			5          & 2          & \textcolor{red}{8} & $ \infty $ & \textcolor{red}{10} & $ \infty $ \\
			\hline
		\end{tabular}
	}
\end{table}

第4步：从距离表中找到从A出发距离最短的顶点（C已经遍历过不需要考虑），也就是顶点B。找到顶点B的邻接点D和E（A已经遍历过不需要考虑）。从B到D的距离是1，所以从A到D的距离是5 + 1 = 6，小于距离表中的8；从B到E的距离是6，所以从A到E的距离是5 + 6 = 11。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|c|c|}
			\hline
			\textbf{B} & \textbf{C} & \textbf{D}         & \textbf{E}          & \textbf{F} & \textbf{G} \\
			\hline
			5          & 2          & \textcolor{red}{6} & \textcolor{red}{11} & 10         & $ \infty $ \\
			\hline
		\end{tabular}
	}
\end{table}

第5步：从距离表中找到从A出发距离最短的顶点（B和C不用考虑），也就是顶点D。找到顶点D的邻接点E和F。从D到E的距离是1，所以从A到E的距离是6 + 1 = 7，小于距离表中的11；从D到F的距离是2，所以从A到F的距离是6 + 2 = 8，小于距离表中的10。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|c|c|}
			\hline
			\textbf{B} & \textbf{C} & \textbf{D} & \textbf{E}         & \textbf{F}         & \textbf{G} \\
			\hline
			5          & 2          & 6          & \textcolor{red}{7} & \textcolor{red}{8} & $ \infty $ \\
			\hline
		\end{tabular}
	}
\end{table}

第6步：从距离表中找到从A出发距离最短的顶点，也就是顶点E。找到顶点E的邻接点G。从E到G的距离是7，所以从A到G的距离是7 + 7 = 14。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|c|c|}
			\hline
			\textbf{B} & \textbf{C} & \textbf{D} & \textbf{E} & \textbf{F} & \textbf{G}          \\
			\hline
			5          & 2          & 6          & 7          & 8          & \textcolor{red}{14} \\
			\hline
		\end{tabular}
	}
\end{table}

第7步：从距离表中找到从A出发距离最短的顶点，也就是顶点F。找到顶点F的邻接点G。从F到G的距离是3，所以从A到G的距离是8 + 3 = 11，小于距离表中的14。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|c|c|}
			\hline
			\textbf{B} & \textbf{C} & \textbf{D} & \textbf{E} & \textbf{F} & \textbf{G}          \\
			\hline
			5          & 2          & 6          & 7          & 8          & \textcolor{red}{11} \\
			\hline
		\end{tabular}
	}
\end{table}

最终，距离表中存储的是从源点A到所有顶点的最短距离。\\

\subsection{多源最短路径算法}

如何能够求出一个带权图中所有顶点两两之间的最短距离呢？\\

对了！刚刚学过了Dijkstra算法，可以对每个顶点都使用一次Dijkstra算法，这样就求出了所有顶点之间的最短距离。\\

这个思路确实可以实现，但是Dijkstra算法的代码逻辑比较复杂，有没有更简单的方法呢？\\

弗洛伊德（Floyd-Warshall）算法是专门用于寻找带权图中多源点之间的最短路径算法。Floyd算法的思想是，若想缩短两点间的距离，仅有一种方式，那就是通过第三顶点绕行。\\

假设$ D^k[i][j] $为路径$ \{i \rightarrow \{l \le k\} \rightarrow j\} $的最小长度。当$ D^{k-1} $已经完成，递推到$ D^k $时：

\begin{enumerate}
	\item 如果$ k \notin \text{最短路径}\{i \rightarrow \{l \le k\} \rightarrow j\} $，则$ D^k = D^{k-1} $。
	\item 如果$ k \in \text{最短路径}\{i \rightarrow \{l \le k\} \rightarrow j\} $，该路径必定由两段最短路径组成，则$ D^k[i][j] = D^{k-1}[i][k] + D^{k-1}[k][j] $。
\end{enumerate}

例如，小哼准备去一些城市旅游，有些城市之间有公路，有些城市之间则没有。为了节省经费以及方便计划旅程，小哼希望在出发之前直到任意两个城市之间的最短路程。\\

如果要让任意两点之间的路程变短，只能引入第三个点，并通过这个顶点中转才有可能缩短原来的路程。这个中转的顶点甚至有时候不只通过一个顶点，而是经过两个或更多点中转会更短。\\

当任意两点之间不允许经过第三个点中转时，这些城市之间的最短路径就是邻接矩阵的初始路径。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\draw (0,0) circle(0.5) node{A};
		\draw (4,0) circle(0.5) node{B};
		\draw (4,4) circle(0.5) node{C};
		\draw (0,4) circle(0.5) node{D};

		\draw[->] (0.5,0) -- (2,0) node[below]{2} -- (3.5,0);
		\draw[->] (0.4,0.25) to[bend right] (3.75,3.6);
		\draw (3,1.5) node{6};
		\draw[->] (3.6,3.75) to[bend right] (0.25,0.4);
		\draw (1,2.5) node{7};
		\draw[->] (0,0.5) -- (0,2) node[left]{4} -- (0,3.5);
		\draw[->] (4,0.5) -- (4,2) node[right]{3} -- (4,3.5);
		\draw[->] (3.5,4) -- (2,4) node[above]{1} -- (0.5,4);
		\draw[->] (-0.5,4) to[bend right] (-0.5,0);
		\draw (-1.5,2) node{5};
		\draw[->] (0,4.5) to[bend left] (4,4.5);
		\draw (2,5.5) node{12};
	\end{tikzpicture}
\end{figure}

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|c|}
			\hline
			           & \textbf{A} & \textbf{B} & \textbf{C} & \textbf{D} \\
			\hline
			\textbf{A} & 0          & 2          & 6          & 4          \\
			\hline
			\textbf{B} & $ \infty $ & 0          & 3          & $ \infty $ \\
			\hline
			\textbf{C} & 7          & $ \infty $ & 0          & 1          \\
			\hline
			\textbf{D} & 5          & $ \infty $ & 12         & 0          \\
			\hline
		\end{tabular}
	}
\end{table}

在只允许经过1号顶点中转的情况下，任意两点之间的最短路程更新为：

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|c|}
			\hline
			           & \textbf{A} & \textbf{B}         & \textbf{C}          & \textbf{D} \\
			\hline
			\textbf{A} & 0          & 2                  & 6                   & 4          \\
			\hline
			\textbf{B} & $ \infty $ & 0                  & 3                   & $ \infty $ \\
			\hline
			\textbf{C} & 7          & \textcolor{red}{9} & 0                   & 1          \\
			\hline
			\textbf{D} & 5          & \textcolor{red}{7} & \textcolor{red}{11} & 0          \\
			\hline
		\end{tabular}
	}
\end{table}

在只允许经过1号和2号顶点中转的情况下，任意两点之间的最短路程更新为：

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|c|}
			\hline
			           & \textbf{A} & \textbf{B} & \textbf{C}          & \textbf{D} \\
			\hline
			\textbf{A} & 0          & 2          & \textcolor{red}{5}  & 4          \\
			\hline
			\textbf{B} & $ \infty $ & 0          & 3                   & $ \infty $ \\
			\hline
			\textbf{C} & 7          & 9          & 0                   & 1          \\
			\hline
			\textbf{D} & 5          & 7          & \textcolor{red}{10} & 0          \\
			\hline
		\end{tabular}
	}
\end{table}

在只允许经过1号、2号和3号顶点中转的情况下，任意两点之间的最短路程更新为：

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|c|}
			\hline
			           & \textbf{A}          & \textbf{B} & \textbf{C} & \textbf{D}         \\
			\hline
			\textbf{A} & 0                   & 2          & 5          & 4                  \\
			\hline
			\textbf{B} & \textcolor{red}{10} & 0          & 3          & \textcolor{red}{4} \\
			\hline
			\textbf{C} & 7                   & 9          & 0          & 1                  \\
			\hline
			\textbf{D} & 5                   & 7          & 10         & 0                  \\
			\hline
		\end{tabular}
	}
\end{table}

最后允许通过所有顶点作为中转，任意两点之间的最短路程更新为：

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|c|}
			\hline
			           & \textbf{A}         & \textbf{B}         & \textbf{C} & \textbf{D} \\
			\hline
			\textbf{A} & 0                  & 2                  & 5          & 4          \\
			\hline
			\textbf{B} & \textcolor{red}{9} & 0                  & 3          & 4          \\
			\hline
			\textbf{C} & \textcolor{red}{6} & \textcolor{red}{8} & 0          & 1          \\
			\hline
			\textbf{D} & 5                  & 7                  & 10         & 0          \\
			\hline
		\end{tabular}
	}
\end{table}

\newpage

\section{最小生成树}

\subsection{最小生成树（MST, Mininum Spanning Tree）}

所谓最小生成树，就是一个图的极小连通子图，它包含原图的所有顶点，并且所有边的权值之和尽可能小。\\

最小生成树需要满足3个条件：

\begin{enumerate}
	\item 是一棵树：树不能有回路，并且$ |V| $个顶点一定有$ |V| - 1 $条边。

	\item 是生成树：包含原图的全部顶点，树的$ |V| - 1 $条边都必须在图里，并且如果向生成树中任意加一条边都一定构成回路。

	\item 边的权重和最小。
\end{enumerate}

如果最小生成树存在，那么图一定连通，反之亦然。\\

例如一个带权图，蓝色边可以把所有顶点连接起来，又保证边的权值和最小。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (-1.5,2) {A};
			\node (B) at (1.5,2) {B};
			\node (C) at (-4,0) {C};
			\node (D) at (0,0) {D};
			\node (E) at (4,0) {E};
			\node (F) at (-1.5,-2) {F};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=black,very thick}]
			\path [->] (B) edge node {7} (E);
			\path [->] (C) edge node {5} (D);
			\path [->] (F) edge node {9} (E);
		\end{scope}

		\begin{scope}[>={Stealth[blue]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=blue,very thick}]
			\path [->] (A) edge node {4} (B);
			\path [->] (A) edge node {3} (C);
			\path [->] (A) edge node {1} (D);
			\path [->] (D) edge node {2} (F);
			\path [->] (D) edge node {3} (E);
		\end{scope}
	\end{tikzpicture}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}[
			level distance=1.5cm,
			level 1/.style={sibling distance=2cm},
			level 2/.style={sibling distance=1.5cm},
			level 3/.style={sibling distance=1cm}
		]
		\node[circle,draw] {A}
		child {node[circle,draw] {B}}
		child {node[circle,draw] {C}}
		child {
				node[circle,draw] {D}
				child {node[circle,draw] {E}}
				child {node[circle,draw] {F}}
			};
	\end{tikzpicture}
	\caption{最小生成树}
\end{figure}

图的最小生成树不是唯一的，同一个图有可能对应多个最小生成树。\\

最小生成树在现实中很很多用处。假如要在若干个城市之间铺设铁路，而预算又是有限的，那么就需要寻找成本最低的铺设方式。城市之间的交通网就像一个连通图，其实并不需要在每两个城市之间都直接进行连接，只需要一个最小生成树，保证所有的城市都有铁路可以达到即可。\\

\subsection{Prim}

Prim算法是以图的顶点为基础，从一个初始顶点开始，寻找达到其它顶点权值最小的边，并把该顶点加入到已触达顶点的集合中。当全部顶点都加入到集合时，算法的工作就完成了。Prim算法的本质是基于贪心算法（greedy algorithm）。\\

Prim算法可以理解为让一棵小树长大，每次找能够向外生长的最小边。\\

例如使用Prim算法获得一个带权图的最小生成树：

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (-1.5,2) {A};
			\node (B) at (1.5,2) {B};
			\node (C) at (-4,0) {C};
			\node (D) at (0,0) {D};
			\node (E) at (4,0) {E};
			\node (F) at (-1.5,-2) {F};
			\node (G) at (1.5,-2) {G};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=black,very thick}]
			\path [-] (A) edge node {2} (B);
			\path [-] (A) edge node {1} (D);
			\path [-] (B) edge node {3} (D);
			\path [-] (B) edge node {10} (E);
			\path [-] (C) edge node {4} (A);
			\path [-] (C) edge node {5} (F);
			\path [-] (D) edge node {2} (C);
			\path [-] (D) edge node {7} (E);
			\path [-] (D) edge node {8} (F);
			\path [-] (D) edge node {4} (G);
			\path [-] (E) edge node {6} (G);
			\path [-] (G) edge node {1} (F);
		\end{scope}
	\end{tikzpicture}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (-1.5,2) {\textcolor{red}{A}};
			\node (B) at (1.5,2) {B};
			\node (C) at (-4,0) {C};
			\node (D) at (0,0) {D};
			\node (E) at (4,0) {E};
			\node (F) at (-1.5,-2) {F};
			\node (G) at (1.5,-2) {G};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=black,very thick}]
			\path [-] (A) edge node {2} (B);
			\path [-] (A) edge node {1} (D);
			\path [-] (B) edge node {3} (D);
			\path [-] (B) edge node {10} (E);
			\path [-] (C) edge node {4} (A);
			\path [-] (C) edge node {5} (F);
			\path [-] (D) edge node {2} (C);
			\path [-] (D) edge node {7} (E);
			\path [-] (D) edge node {8} (F);
			\path [-] (D) edge node {4} (G);
			\path [-] (E) edge node {6} (G);
			\path [-] (G) edge node {1} (F);
		\end{scope}
	\end{tikzpicture}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (-1.5,2) {\textcolor{red}{A}};
			\node (B) at (1.5,2) {B};
			\node (C) at (-4,0) {C};
			\node (D) at (0,0) {\textcolor{red}{D}};
			\node (E) at (4,0) {E};
			\node (F) at (-1.5,-2) {F};
			\node (G) at (1.5,-2) {G};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=black,very thick}]
			\path [-] (A) edge node {2} (B);
			\path [-] (B) edge node {3} (D);
			\path [-] (B) edge node {10} (E);
			\path [-] (C) edge node {4} (A);
			\path [-] (C) edge node {5} (F);
			\path [-] (D) edge node {2} (C);
			\path [-] (D) edge node {7} (E);
			\path [-] (D) edge node {8} (F);
			\path [-] (D) edge node {4} (G);
			\path [-] (E) edge node {6} (G);
			\path [-] (G) edge node {1} (F);
		\end{scope}

		\begin{scope}[>={Stealth[red]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=red,very thick}]
			\path [-] (A) edge node {1} (D);
		\end{scope}
	\end{tikzpicture}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (-1.5,2) {\textcolor{red}{A}};
			\node (B) at (1.5,2) {\textcolor{red}{B}};
			\node (C) at (-4,0) {C};
			\node (D) at (0,0) {\textcolor{red}{D}};
			\node (E) at (4,0) {E};
			\node (F) at (-1.5,-2) {F};
			\node (G) at (1.5,-2) {G};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=black,very thick}]
			\path [-] (B) edge node {3} (D);
			\path [-] (B) edge node {10} (E);
			\path [-] (C) edge node {4} (A);
			\path [-] (C) edge node {5} (F);
			\path [-] (D) edge node {2} (C);
			\path [-] (D) edge node {7} (E);
			\path [-] (D) edge node {8} (F);
			\path [-] (D) edge node {4} (G);
			\path [-] (E) edge node {6} (G);
			\path [-] (G) edge node {1} (F);
		\end{scope}

		\begin{scope}[>={Stealth[red]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=red,very thick}]
			\path [-] (A) edge node {1} (D);
			\path [-] (A) edge node {2} (B);
		\end{scope}
	\end{tikzpicture}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (-1.5,2) {\textcolor{red}{A}};
			\node (B) at (1.5,2) {\textcolor{red}{B}};
			\node (C) at (-4,0) {\textcolor{red}{C}};
			\node (D) at (0,0) {\textcolor{red}{D}};
			\node (E) at (4,0) {E};
			\node (F) at (-1.5,-2) {F};
			\node (G) at (1.5,-2) {G};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=black,very thick}]
			\path [-] (B) edge node {3} (D);
			\path [-] (B) edge node {10} (E);
			\path [-] (C) edge node {4} (A);
			\path [-] (C) edge node {5} (F);
			\path [-] (D) edge node {7} (E);
			\path [-] (D) edge node {8} (F);
			\path [-] (D) edge node {4} (G);
			\path [-] (E) edge node {6} (G);
			\path [-] (G) edge node {1} (F);
		\end{scope}

		\begin{scope}[>={Stealth[red]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=red,very thick}]
			\path [-] (A) edge node {1} (D);
			\path [-] (A) edge node {2} (B);
			\path [-] (D) edge node {2} (C);
		\end{scope}
	\end{tikzpicture}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (-1.5,2) {\textcolor{red}{A}};
			\node (B) at (1.5,2) {\textcolor{red}{B}};
			\node (C) at (-4,0) {\textcolor{red}{C}};
			\node (D) at (0,0) {\textcolor{red}{D}};
			\node (E) at (4,0) {E};
			\node (F) at (-1.5,-2) {F};
			\node (G) at (1.5,-2) {\textcolor{red}{G}};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=black,very thick}]
			\path [-] (B) edge node {3} (D);
			\path [-] (B) edge node {10} (E);
			\path [-] (C) edge node {4} (A);
			\path [-] (C) edge node {5} (F);
			\path [-] (D) edge node {7} (E);
			\path [-] (D) edge node {8} (F);
			\path [-] (E) edge node {6} (G);
			\path [-] (G) edge node {1} (F);
		\end{scope}

		\begin{scope}[>={Stealth[red]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=red,very thick}]
			\path [-] (A) edge node {1} (D);
			\path [-] (A) edge node {2} (B);
			\path [-] (D) edge node {2} (C);
			\path [-] (D) edge node {4} (G);
		\end{scope}
	\end{tikzpicture}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (-1.5,2) {\textcolor{red}{A}};
			\node (B) at (1.5,2) {\textcolor{red}{B}};
			\node (C) at (-4,0) {\textcolor{red}{C}};
			\node (D) at (0,0) {\textcolor{red}{D}};
			\node (E) at (4,0) {E};
			\node (F) at (-1.5,-2) {\textcolor{red}{F}};
			\node (G) at (1.5,-2) {\textcolor{red}{G}};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=black,very thick}]
			\path [-] (B) edge node {3} (D);
			\path [-] (B) edge node {10} (E);
			\path [-] (C) edge node {4} (A);
			\path [-] (C) edge node {5} (F);
			\path [-] (D) edge node {7} (E);
			\path [-] (D) edge node {8} (F);
			\path [-] (E) edge node {6} (G);
		\end{scope}

		\begin{scope}[>={Stealth[red]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=red,very thick}]
			\path [-] (A) edge node {1} (D);
			\path [-] (A) edge node {2} (B);
			\path [-] (D) edge node {2} (C);
			\path [-] (D) edge node {4} (G);
			\path [-] (G) edge node {1} (F);
		\end{scope}
	\end{tikzpicture}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (-1.5,2) {\textcolor{red}{A}};
			\node (B) at (1.5,2) {\textcolor{red}{B}};
			\node (C) at (-4,0) {\textcolor{red}{C}};
			\node (D) at (0,0) {\textcolor{red}{D}};
			\node (E) at (4,0) {\textcolor{red}{E}};
			\node (F) at (-1.5,-2) {\textcolor{red}{F}};
			\node (G) at (1.5,-2) {\textcolor{red}{G}};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=black,very thick}]
			\path [-] (B) edge node {3} (D);
			\path [-] (B) edge node {10} (E);
			\path [-] (C) edge node {4} (A);
			\path [-] (C) edge node {5} (F);
			\path [-] (D) edge node {7} (E);
			\path [-] (D) edge node {8} (F);
		\end{scope}

		\begin{scope}[>={Stealth[red]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=red,very thick}]
			\path [-] (A) edge node {1} (D);
			\path [-] (A) edge node {2} (B);
			\path [-] (D) edge node {2} (C);
			\path [-] (D) edge node {4} (G);
			\path [-] (G) edge node {1} (F);
			\path [-] (E) edge node {6} (G);
		\end{scope}
	\end{tikzpicture}
\end{figure}

\vspace{0.5cm}

\subsection{Kruskal}

与Prim算法不同，Prim算法是以顶点为关键来获得最小生成树的，而Kruskal算法是以边为关键获得最小生成树的。\\

Kruskal算法可以理解为将森林合并成树，每次在图中找权值最小的边收录。\\

例如使用Kruskal算法获得一个带权图的最小生成树：

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (-1.5,2) {\textcolor{red}{A}};
			\node (B) at (1.5,2) {B};
			\node (C) at (-4,0) {C};
			\node (D) at (0,0) {\textcolor{red}{D}};
			\node (E) at (4,0) {E};
			\node (F) at (-1.5,-2) {F};
			\node (G) at (1.5,-2) {G};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=black,very thick}]
			\path [-] (A) edge node {2} (B);
			\path [-] (B) edge node {3} (D);
			\path [-] (B) edge node {10} (E);
			\path [-] (C) edge node {4} (A);
			\path [-] (C) edge node {5} (F);
			\path [-] (D) edge node {2} (C);
			\path [-] (D) edge node {7} (E);
			\path [-] (D) edge node {8} (F);
			\path [-] (D) edge node {4} (G);
			\path [-] (E) edge node {6} (G);
			\path [-] (G) edge node {1} (F);
		\end{scope}

		\begin{scope}[>={Stealth[red]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=red,very thick}]
			\path [-] (A) edge node {1} (D);
		\end{scope}
	\end{tikzpicture}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (-1.5,2) {\textcolor{red}{A}};
			\node (B) at (1.5,2) {B};
			\node (C) at (-4,0) {C};
			\node (D) at (0,0) {\textcolor{red}{D}};
			\node (E) at (4,0) {E};
			\node (F) at (-1.5,-2) {\textcolor{red}{F}};
			\node (G) at (1.5,-2) {\textcolor{red}{G}};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=black,very thick}]
			\path [-] (A) edge node {2} (B);
			\path [-] (B) edge node {3} (D);
			\path [-] (B) edge node {10} (E);
			\path [-] (C) edge node {4} (A);
			\path [-] (C) edge node {5} (F);
			\path [-] (D) edge node {2} (C);
			\path [-] (D) edge node {7} (E);
			\path [-] (D) edge node {8} (F);
			\path [-] (D) edge node {4} (G);
			\path [-] (E) edge node {6} (G);
		\end{scope}

		\begin{scope}[>={Stealth[red]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=red,very thick}]
			\path [-] (A) edge node {1} (D);
			\path [-] (G) edge node {1} (F);
		\end{scope}
	\end{tikzpicture}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (-1.5,2) {\textcolor{red}{A}};
			\node (B) at (1.5,2) {B};
			\node (C) at (-4,0) {\textcolor{red}{C}};
			\node (D) at (0,0) {\textcolor{red}{D}};
			\node (E) at (4,0) {E};
			\node (F) at (-1.5,-2) {\textcolor{red}{F}};
			\node (G) at (1.5,-2) {\textcolor{red}{G}};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=black,very thick}]
			\path [-] (A) edge node {2} (B);
			\path [-] (B) edge node {3} (D);
			\path [-] (B) edge node {10} (E);
			\path [-] (C) edge node {4} (A);
			\path [-] (C) edge node {5} (F);
			\path [-] (D) edge node {7} (E);
			\path [-] (D) edge node {8} (F);
			\path [-] (D) edge node {4} (G);
			\path [-] (E) edge node {6} (G);
		\end{scope}

		\begin{scope}[>={Stealth[red]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=red,very thick}]
			\path [-] (A) edge node {1} (D);
			\path [-] (G) edge node {1} (F);
			\path [-] (D) edge node {2} (C);
		\end{scope}
	\end{tikzpicture}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (-1.5,2) {\textcolor{red}{A}};
			\node (B) at (1.5,2) {\textcolor{red}{B}};
			\node (C) at (-4,0) {\textcolor{red}{C}};
			\node (D) at (0,0) {\textcolor{red}{D}};
			\node (E) at (4,0) {E};
			\node (F) at (-1.5,-2) {\textcolor{red}{F}};
			\node (G) at (1.5,-2) {\textcolor{red}{G}};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=black,very thick}]
			\path [-] (B) edge node {3} (D);
			\path [-] (B) edge node {10} (E);
			\path [-] (C) edge node {4} (A);
			\path [-] (C) edge node {5} (F);
			\path [-] (D) edge node {7} (E);
			\path [-] (D) edge node {8} (F);
			\path [-] (D) edge node {4} (G);
			\path [-] (E) edge node {6} (G);
		\end{scope}

		\begin{scope}[>={Stealth[red]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=red,very thick}]
			\path [-] (A) edge node {1} (D);
			\path [-] (G) edge node {1} (F);
			\path [-] (D) edge node {2} (C);
			\path [-] (A) edge node {2} (B);
		\end{scope}
	\end{tikzpicture}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (-1.5,2) {\textcolor{red}{A}};
			\node (B) at (1.5,2) {\textcolor{red}{B}};
			\node (C) at (-4,0) {\textcolor{red}{C}};
			\node (D) at (0,0) {\textcolor{red}{D}};
			\node (E) at (4,0) {E};
			\node (F) at (-1.5,-2) {\textcolor{red}{F}};
			\node (G) at (1.5,-2) {\textcolor{red}{G}};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=black,very thick}]
			\path [-] (B) edge node {3} (D);
			\path [-] (B) edge node {10} (E);
			\path [-] (C) edge node {4} (A);
			\path [-] (C) edge node {5} (F);
			\path [-] (D) edge node {7} (E);
			\path [-] (D) edge node {8} (F);
			\path [-] (E) edge node {6} (G);
		\end{scope}

		\begin{scope}[>={Stealth[red]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=red,very thick}]
			\path [-] (A) edge node {1} (D);
			\path [-] (G) edge node {1} (F);
			\path [-] (D) edge node {2} (C);
			\path [-] (A) edge node {2} (B);
			\path [-] (D) edge node {4} (G);
		\end{scope}
	\end{tikzpicture}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\begin{scope}[every node/.style={circle,thick,draw}]
			\node (A) at (-1.5,2) {\textcolor{red}{A}};
			\node (B) at (1.5,2) {\textcolor{red}{B}};
			\node (C) at (-4,0) {\textcolor{red}{C}};
			\node (D) at (0,0) {\textcolor{red}{D}};
			\node (E) at (4,0) {\textcolor{red}{E}};
			\node (F) at (-1.5,-2) {\textcolor{red}{F}};
			\node (G) at (1.5,-2) {\textcolor{red}{G}};
		\end{scope}

		\begin{scope}[>={Stealth[black]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=black,very thick}]
			\path [-] (B) edge node {3} (D);
			\path [-] (B) edge node {10} (E);
			\path [-] (C) edge node {4} (A);
			\path [-] (C) edge node {5} (F);
			\path [-] (D) edge node {7} (E);
			\path [-] (D) edge node {8} (F);
		\end{scope}

		\begin{scope}[>={Stealth[red]},
			every node/.style={fill=white,circle},
			every edge/.style={draw=red,very thick}]
			\path [-] (A) edge node {1} (D);
			\path [-] (G) edge node {1} (F);
			\path [-] (D) edge node {2} (C);
			\path [-] (A) edge node {2} (B);
			\path [-] (D) edge node {4} (G);
			\path [-] (E) edge node {6} (G);
		\end{scope}
	\end{tikzpicture}
\end{figure}

\newpage

\section{欧拉图与哈密尔顿图}

\subsection{欧拉图（Euler Graph）}

Konigsberg被一条河流分成4块区域，有7座桥把这4块区域连接了起来。镇上的人们想弄明白是否可能从某块区域出发，不重复地经过所有桥并且回到出发点。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}[x=10cm, y=9.19cm]
		%water
		\filldraw[water] (0, 0) -- (0, 1) -- (1, 1) -- (1, 0) -- cycle;

		%bridge top 1
		\filldraw[bridge] ($(0, 1) + (0.329, -0.300)$) --
		($(0, 1) + (0.423, -0.301)$) -- ($(0, 1) + (0.399, -0.399)$) --
		($(0, 1) + (0.328, -0.404)$) -- cycle;
		\draw[contour] ($(0, 1) + (0.423, -0.301)$) -- ($(0, 1) + (0.399, -0.399)$)
		($(0, 1) + (0.328, -0.404)$) -- ($(0, 1) + (0.329, -0.300)$);

		%bridge top 2
		\filldraw[bridge] ($(0, 1) + (0.532, -0.302)$) --
		($(0, 1) + (0.558, -0.310)$) -- ($(0, 1) + (0.591, -0.338)$) --
		($(0, 1) + (0.609, -0.404)$) -- ($(0, 1) + (0.549, -0.388)$) --
		cycle;
		\draw[contour] ($(0, 1) + (0.591, -0.338)$) -- ($(0, 1) + (0.609, -0.404)$)
		($(0, 1) + (0.532, -0.302)$) -- ($(0, 1) + (0.549, -0.388)$);

		%bridge top 3
		\filldraw[bridge] ($(0, 1) + (0.635, -0.328)$) --
		($(0, 1) + (0.656, -0.304)$) -- ($(0, 1) + (0.669, -0.276)$) --
		($(0, 1) + (0.796, -0.364)$) --
		($(0, 1) + (0.776, -0.396)$) -- ($(0, 1) + (0.762, -0.420)$) -- cycle;
		\draw[contour] ($(0, 1) + (0.635, -0.328)$) -- ($(0, 1) + (0.762, -0.420)$)
		($(0, 1) + (0.669, -0.276)$) -- ($(0, 1) + (0.796, -0.364)$);

		%bridge middle right
		\filldraw[bridge] ($(0, 1) + (0.658, -0.590)$) --
		($(0, 1) + (0.668, -0.546)$) -- ($(0, 1) + (0.778, -0.524)$) --
		($(0, 1) + (0.792, -0.554)$) -- ($(0, 1) + (0.796, -0.590)$) --cycle;
		\draw[contour] ($(0, 1) + (0.668, -0.546)$) -- ($(0, 1) + (0.778, -0.524)$)
		($(0, 1) + (0.658, -0.590)$) -- ($(0, 1) + (0.796, -0.590)$);

		%bridge bottom 1
		\filldraw[bridge] ($(0, 1) + (0.350, -0.826)$) --
		($(0, 1) + (0.410, -0.804)$) -- ($(0, 1) + (0.422, -0.794)$) --
		($(0, 1) + (0.412, -0.708)$) -- ($(0, 1) + (0.372, -0.702)$) --
		($(0, 1) + (0.336, -0.695)$) -- cycle;
		\draw[contour] ($(0, 1) + (0.422, -0.794)$) -- ($(0, 1) + (0.412, -0.708)$)
		($(0, 1) + (0.350, -0.826)$) -- ($(0, 1) + (0.336, -0.695)$);

		%bridge bottom 2
		\filldraw[bridge] ($(0, 1) + (0.596, -0.700)$) --
		($(0, 1) + (0.535, -0.708)$) -- ($(0, 1) + (0.523, -0.784)$) --
		($(0, 1) + (0.581, -0.777)$) -- cycle;
		\draw[contour] ($(0, 1) + (0.535, -0.708)$) -- ($(0, 1) + (0.523, -0.784)$)
		($(0, 1) + (0.596, -0.700)$) -- ($(0, 1) + (0.581, -0.777)$);

		%bridge bottom 3
		\filldraw[bridge] ($(0, 1) + (0.581, -0.777)$) --
		($(0, 1) + (0.660, -0.862)$) -- ($(0, 1) + (0.858, -0.717)$) --
		($(0, 1) + (0.837, -0.702)$) -- ($(0, 1) + (0.826, -0.688)$) --
		($(0, 1) + (0.785, -0.668)$) -- cycle;
		\draw[contour] ($(0, 1) + (0.581, -0.777)$) -- ($(0, 1) + (0.785, -0.668)$)
		($(0, 1) + (0.660, -0.862)$) -- ($(0, 1) + (0.858, -0.717)$);

		%land top
		\filldraw[land] (0, 1) --
		($(0, 1) + (0, -0.287)$) -- ($(0, 1) + (0.080, -0.287)$) --
		($(0, 1) + (0.161, -0.281)$) -- ($(0, 1) + (0.178, -0.273)$) --
		($(0, 1) + (0.257, -0.289)$) -- ($(0, 1) + (0.280, -0.287)$) --
		($(0, 1) + (0.329, -0.300)$) -- ($(0, 1) + (0.423, -0.301)$) --
		($(0, 1) + (0.532, -0.302)$) -- ($(0, 1) + (0.558, -0.310)$) --
		($(0, 1) + (0.591, -0.338)$) -- ($(0, 1) + (0.635, -0.328)$) --
		($(0, 1) + (0.656, -0.304)$) -- ($(0, 1) + (0.669, -0.276)$) --
		($(0, 1) + (0.720, -0.246)$) -- ($(0, 1) + (0.741, -0.233)$) --
		($(0, 1) + (0.780, -0.210)$) -- ($(0, 1) + (0.824, -0.206)$) --
		($(0, 1) + (0.874, -0.178)$) -- ($(0, 1) + (0.931, -0.169)$) --
		($(0, 1) + (0.969, -0.161)$) -- ($(1, 1) + (0, -0.149)$) --
		(1, 1) -- cycle;
		\draw[contour] ($(0, 1) + (0, -0.287)$) -- ($(0, 1) + (0.080, -0.287)$) --
		($(0, 1) + (0.161, -0.281)$) -- ($(0, 1) + (0.178, -0.273)$) --
		($(0, 1) + (0.257, -0.289)$) -- ($(0, 1) + (0.280, -0.287)$) --
		($(0, 1) + (0.329, -0.300)$) -- ($(0, 1) + (0.423, -0.301)$) --
		($(0, 1) + (0.532, -0.302)$) -- ($(0, 1) + (0.558, -0.310)$) --
		($(0, 1) + (0.591, -0.338)$) -- ($(0, 1) + (0.635, -0.328)$) --
		($(0, 1) + (0.656, -0.304)$) -- ($(0, 1) + (0.669, -0.276)$) --
		($(0, 1) + (0.720, -0.246)$) -- ($(0, 1) + (0.741, -0.233)$) --
		($(0, 1) + (0.780, -0.210)$) -- ($(0, 1) + (0.824, -0.206)$) --
		($(0, 1) + (0.874, -0.178)$) -- ($(0, 1) + (0.931, -0.169)$) --
		($(0, 1) + (0.969, -0.161)$) -- ($(1, 1) + (0, -0.149)$);

		%land bottom
		\filldraw[land] ($(0, 1) + (0, -0.890)$) -- ($(0, 1) + (0.067, -0.880)$) --
		($(0, 1) + (0.067, -0.880)$) -- ($(0, 1) + (0.085, -0.860)$) --
		($(0, 1) + (0.111, -0.858)$) -- ($(0, 1) + (0.139, -0.849)$) --
		($(0, 1) + (0.161, -0.860)$) -- ($(0, 1) + (0.212, -0.847)$) --
		($(0, 1) + (0.242, -0.830)$) -- ($(0, 1) + (0.350, -0.826)$) --
		($(0, 1) + (0.410, -0.804)$) -- ($(0, 1) + (0.422, -0.794)$) --
		($(0, 1) + (0.450, -0.784)$) -- ($(0, 1) + (0.523, -0.784)$) --
		($(0, 1) + (0.581, -0.777)$) -- ($(0, 1) + (0.660, -0.862)$) --
		($(0, 1) + (0.672, -0.882)$) -- ($(0, 1) + (0.679, -0.924)$) --
		($(0, 1) + (0.698, -0.968)$) -- ($(0, 1) + (0.714, -0.990)$) --
		(0.718, 0) -- (0, 0) -- cycle;
		\draw[contour] ($(0, 1) + (0, -0.890)$) -- ($(0, 1) + (0.067, -0.880)$) --
		($(0, 1) + (0.067, -0.880)$) -- ($(0, 1) + (0.085, -0.860)$) --
		($(0, 1) + (0.111, -0.858)$) -- ($(0, 1) + (0.139, -0.849)$) --
		($(0, 1) + (0.161, -0.860)$) -- ($(0, 1) + (0.212, -0.847)$) --
		($(0, 1) + (0.242, -0.830)$) -- ($(0, 1) + (0.350, -0.826)$) --
		($(0, 1) + (0.410, -0.804)$) -- ($(0, 1) + (0.422, -0.794)$) --
		($(0, 1) + (0.450, -0.784)$) -- ($(0, 1) + (0.523, -0.784)$) --
		($(0, 1) + (0.581, -0.777)$) -- ($(0, 1) + (0.660, -0.862)$) --
		($(0, 1) + (0.672, -0.882)$) -- ($(0, 1) + (0.679, -0.924)$) --
		($(0, 1) + (0.698, -0.968)$) -- ($(0, 1) + (0.714, -0.990)$) --
		(0.718, 0);

		%land right
		\filldraw[land] (1, 0) -- ($(0, 1) + (0.978, -0.975)$) --
		($(0, 1) + (0.954, -0.908)$) -- ($(0, 1) + (0.921, -0.829)$) --
		($(0, 1) + (0.900, -0.810)$) -- ($(0, 1) + (0.880, -0.775)$) --
		($(0, 1) + (0.858, -0.717)$) -- ($(0, 1) + (0.837, -0.702)$) --
		($(0, 1) + (0.826, -0.688)$) -- ($(0, 1) + (0.785, -0.668)$) --
		($(0, 1) + (0.796, -0.623)$) -- ($(0, 1) + (0.796, -0.590)$) --
		($(0, 1) + (0.792, -0.554)$) -- ($(0, 1) + (0.778, -0.524)$) --
		($(0, 1) + (0.764, -0.466)$) -- ($(0, 1) + (0.762, -0.420)$) --
		($(0, 1) + (0.776, -0.396)$) -- ($(0, 1) + (0.796, -0.364)$) --
		($(0, 1) + (0.838, -0.368)$) -- ($(0, 1) + (0.864, -0.380)$) --
		($(0, 1) + (0.910, -0.384)$) -- ($(0, 1) + (0.946, -0.392)$) --
		($(0, 1) + (0.971, -0.394)$) -- ($(0, 1) + (1, -0.414)$) -- cycle;
		\draw[contour] (1, 0) -- ($(0, 1) + (0.978, -0.975)$) --
		($(0, 1) + (0.954, -0.908)$) -- ($(0, 1) + (0.921, -0.829)$) --
		($(0, 1) + (0.900, -0.810)$) -- ($(0, 1) + (0.880, -0.775)$) --
		($(0, 1) + (0.858, -0.717)$) -- ($(0, 1) + (0.837, -0.702)$) --
		($(0, 1) + (0.826, -0.688)$) -- ($(0, 1) + (0.785, -0.668)$) --
		($(0, 1) + (0.796, -0.623)$) -- ($(0, 1) + (0.796, -0.590)$) --
		($(0, 1) + (0.792, -0.554)$) -- ($(0, 1) + (0.778, -0.524)$) --
		($(0, 1) + (0.764, -0.466)$) -- ($(0, 1) + (0.762, -0.420)$) --
		($(0, 1) + (0.776, -0.396)$) -- ($(0, 1) + (0.796, -0.364)$) --
		($(0, 1) + (0.838, -0.368)$) -- ($(0, 1) + (0.864, -0.380)$) --
		($(0, 1) + (0.910, -0.384)$) -- ($(0, 1) + (0.946, -0.392)$) --
		($(0, 1) + (0.971, -0.394)$) -- ($(0, 1) + (1, -0.414)$);

		%island
		\filldraw[land] ($(0, 1) + (0.241, -0.622)$) -- ($(0, 1) + (0.235, -0.587)$) --
		($(0, 1) + (0.240, -0.540)$) -- ($(0, 1) + (0.249, -0.524)$) --
		($(0, 1) + (0.252, -0.498)$) -- ($(0, 1) + (0.266, -0.482)$) --
		($(0, 1) + (0.271, -0.462)$) -- ($(0, 1) + (0.288, -0.454)$) --
		($(0, 1) + (0.300, -0.434)$) -- ($(0, 1) + (0.308, -0.418)$) --
		($(0, 1) + (0.320, -0.412)$) -- ($(0, 1) + (0.328, -0.404)$) --
		($(0, 1) + (0.399, -0.399)$) -- ($(0, 1) + (0.453, -0.393)$) --
		($(0, 1) + (0.518, -0.386)$) -- ($(0, 1) + (0.549, -0.388)$) --
		($(0, 1) + (0.609, -0.404)$) -- ($(0, 1) + (0.624, -0.410)$) --
		($(0, 1) + (0.644, -0.438)$) -- ($(0, 1) + (0.663, -0.486)$) --
		($(0, 1) + (0.670, -0.519)$) -- ($(0, 1) + (0.668, -0.546)$) --
		($(0, 1) + (0.658, -0.590)$) -- ($(0, 1) + (0.648, -0.612)$) --
		($(0, 1) + (0.636, -0.648)$) -- ($(0, 1) + (0.633, -0.666)$) --
		($(0, 1) + (0.617, -0.677)$) -- ($(0, 1) + (0.596, -0.700)$) --
		($(0, 1) + (0.535, -0.708)$) -- ($(0, 1) + (0.500, -0.709)$) --
		($(0, 1) + (0.457, -0.717)$) -- ($(0, 1) + (0.412, -0.708)$) --
		($(0, 1) + (0.372, -0.702)$) -- ($(0, 1) + (0.336, -0.695)$) --
		($(0, 1) + (0.291, -0.679)$) -- ($(0, 1) + (0.268, -0.652)$) --
		cycle;
		\draw[contour] ($(0, 1) + (0.241, -0.622)$) -- ($(0, 1) + (0.235, -0.587)$) --
		($(0, 1) + (0.240, -0.540)$) -- ($(0, 1) + (0.249, -0.524)$) --
		($(0, 1) + (0.252, -0.498)$) -- ($(0, 1) + (0.266, -0.482)$) --
		($(0, 1) + (0.271, -0.462)$) -- ($(0, 1) + (0.288, -0.454)$) --
		($(0, 1) + (0.300, -0.434)$) -- ($(0, 1) + (0.308, -0.418)$) --
		($(0, 1) + (0.320, -0.412)$) -- ($(0, 1) + (0.328, -0.404)$) --
		($(0, 1) + (0.399, -0.399)$) -- ($(0, 1) + (0.453, -0.393)$) --
		($(0, 1) + (0.518, -0.386)$) -- ($(0, 1) + (0.549, -0.388)$) --
		($(0, 1) + (0.609, -0.404)$) -- ($(0, 1) + (0.624, -0.410)$) --
		($(0, 1) + (0.644, -0.438)$) -- ($(0, 1) + (0.663, -0.486)$) --
		($(0, 1) + (0.670, -0.519)$) -- ($(0, 1) + (0.668, -0.546)$) --
		($(0, 1) + (0.658, -0.590)$) -- ($(0, 1) + (0.648, -0.612)$) --
		($(0, 1) + (0.636, -0.648)$) -- ($(0, 1) + (0.633, -0.666)$) --
		($(0, 1) + (0.617, -0.677)$) -- ($(0, 1) + (0.596, -0.700)$) --
		($(0, 1) + (0.535, -0.708)$) -- ($(0, 1) + (0.500, -0.709)$) --
		($(0, 1) + (0.457, -0.717)$) -- ($(0, 1) + (0.412, -0.708)$) --
		($(0, 1) + (0.372, -0.702)$) -- ($(0, 1) + (0.336, -0.695)$) --
		($(0, 1) + (0.291, -0.679)$) -- ($(0, 1) + (0.268, -0.652)$) --
		($(0, 1) + (0.241, -0.622)$);
	\end{tikzpicture}
	\caption{哥尼斯堡七桥问题}
\end{figure}

这个问题可以用图进行描述，顶点用于表示4块区域，边用于表示连接两个区域的桥。这样问题就转化成了能否不重复地一笔画完所有的边，即图是否存在欧拉回路（Euler Circuit）。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		[lineDecorate/.style={-,thick},
			nodeDecorate/.style={shape=circle,inner sep=2pt,draw,thick}]
		\foreach \nodename/\x/\y/\direction/\navigate in {
				a/0/0/left/west, b/0/2/left/west, c/0/4/left/west, d/4/2/right/east}
			{
				\node (\nodename) at (\x,\y) [nodeDecorate] {};
				\node [\direction] at (\nodename.\navigate) {\footnotesize$\nodename$};
			}
		\path
		\foreach \startnode/\endnode in {a/d, b/d, c/d}
			{
				(\startnode) edge[lineDecorate] node {} (\endnode)
			}
		\foreach \startnode/\endnode in {a/b, b/c, c/b, b/a}
			{
				(\startnode) edge[lineDecorate,bend left] node {} (\endnode)
			};
	\end{tikzpicture}
\end{figure}

1736年，29岁的欧拉向圣彼得堡科学院递交了关于哥尼斯堡七桥问题的论文。在解答问题的同时，开创了数学的一个新的分支——图论与几何拓扑，也由此展开了数学史上的新历程。\\

七桥问题提出后，很多人对此很感兴趣，纷纷进行试验，但在相当长的时间里，始终未能解决。欧拉通过对七桥问题的研究，不仅圆满地回答了哥尼斯堡居民提出的问题，而且得到并证明了更为广泛的有关一笔画的三条结论。\\

欧拉通路（Euler Trail）与欧拉回路的区别在于，欧拉通路需要经过图中所有边正好一次，而欧拉回路则需要经过图中所有边正好一次并最终回到出发点。

\begin{tcolorbox}
	\mybox{Exercise}
	判断在一个有度为奇数的顶点的图中是否存在一条欧拉回路。\\
	假设图G存在欧拉回路，令v为回路中的第一个顶点。从第一个顶点出发离开会使当前顶点的度增加1。\\
	经过回路中的中间顶点时，每个顶点的度都会增加2，一个入度，一个出度。\\
	最后一条边必须回到第一个顶点v，这样会使第一个顶点v的度增加1。\\
	因为每一个顶点都有可能作为出发点，因此只有顶点度都为偶数的图才有可能存在欧拉回路。
\end{tcolorbox}

一个连通图存在欧拉通路但无欧拉回路，当且仅当它恰好拥有2个度为奇数的顶点。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\node[black, fill=black, circle, inner sep=2pt] at (0,0){};
		\node[black, fill=black, circle, inner sep=2pt, label=left:end] at (0,2){};
		\node[black, fill=black, circle, inner sep=2pt] at (0,4){};
		\node[black, fill=black, circle, inner sep=2pt] at (2,0){};
		\node[black, fill=black, circle, inner sep=2pt] at (2,2){};
		\node[black, fill=black, circle, inner sep=2pt] at (2,4){};
		\node[black, fill=black, circle, inner sep=2pt] at (4,0){};
		\node[black, fill=black, circle, inner sep=2pt, label=right:start] at (4,2){};
		\node[black, fill=black, circle, inner sep=2pt] at (4,4){};
		\node[black, fill=black, circle, inner sep=2pt] at (6,0){};
		\node[black, fill=black, circle, inner sep=2pt] at (6,4){};

		\draw[blue, very thick, ->] (4,1.8) node[right, red]{1} -- (4,0.2);
		\draw[blue, very thick, ->] (4.2,0) node[below, red]{2} -- (5.8,0);
		\draw[blue, very thick, ->] (6,0.2) node[right, red]{3} -- (6,3.8);
		\draw[blue, very thick, ->] (5.8,4) node[above, red]{4} -- (4.2,4);
		\draw[blue, very thick, ->] (4,3.8) node[right, red]{5} -- (4,2.2);
		\draw[blue, very thick, ->] (3.8,2) node[above, red]{6} -- (2.2,2);
		\draw[blue, very thick, ->] (2,1.8) node[left, red]{7} -- (2,0.2);
		\draw[blue, very thick, ->] (1.8,0) node[below, red]{8} -- (0.2,0);
		\draw[blue, very thick, ->] (0,0.2) node[left, red]{9} -- (0,1.8);
		\draw[blue, very thick, ->] (0.2,2) node[below, red]{10} -- (1.8,2);
		\draw[blue, very thick, ->] (2,2.2) node[above, red]{11} -- (2,3.8);
		\draw[blue, very thick, ->] (2.2,4) node[below, red]{12} -- (3.8,4);
		\draw[blue, very thick, ->] (4,4.2) node[above, red]{13} -- (4,5) -- (2,5) -- (2,4.2);
		\draw[blue, very thick, ->] (1.8,4) node[left, red]{14} -- (0.2,4);
		\draw[blue, very thick, ->] (0,3.8) node[left, red]{15} -- (0,2.2);
	\end{tikzpicture}
	\caption{欧拉通路}
\end{figure}

\vspace{0.5cm}

\subsection{哈密尔顿图（Hamiltonian）}

与欧拉图相似的另一个问题是，是否存在一条通路可以把图中所有顶点都正好访问一次？\\

在图G中，如果一条从顶点S到T的路径不重复地经过每个顶点，那么这条路径成为哈密尔顿通路（Hamilton Path）。\\

在图G中，如果一条从顶点S到S的路径不重复地经过每个顶点（顶点S经过两次），那么这条路径成为哈密尔顿回路（Hamilton Cycle）。\\

如果图G中存在哈密尔顿回路，则称图G为哈密尔顿图。\\

关于哈密尔顿图存在以下几个定理：

\begin{itemize}
	\item 所有完全图$ K_n\ (n \ge 3) $都是哈密尔顿图。

	\item 所有完全图$ C_n $都是哈密尔顿图。

	\item 狄拉克定理（Dirac's Theorem）：如果G是有$ n\ (n \ge 3) $个顶点的简单图，且每个顶点的度都至少为$ n \over 2 $，则G有哈密尔顿回路。

	\item 欧尔定理（Ore's Theorem）：如果G是有$ n\ (n \ge 3) $个顶点的简单图，且对于每一对不相邻的顶点$ u $和$ v $，都满足$ deg(u) + deg(v) \ge n $，则G有哈密尔顿回路。
\end{itemize}

\newpage

\section{平面图}

\subsection{平面图（Planar Graph）}

在设计电路图和流程图时，通常希望连接线之间尽量不发生交叉。如果可以在平面中画出一个图，而边没有任何交叉，则这个图是平面图。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}[scale=1.6]
		\draw[color=black, thick]
		(0,0) to [short,o-] (6,0){}
		(0,1) node[]{\large{\textbf{INPUT}}}
		(5,0) node[ground]{} node[circ](4.5,0){}
		(0,2) to [pC, l=$C_1$, o-] (0.5,2)
		to [R,l=$R_1$,](1.5,2)
		to node[short]{}(2.6,2)
		(1.5,2) to [C, l=$C_2$, *-] (1.5,3) -| (5,3)
		(2.2,2) to [R, l=$R_2$, *-*] (2.2,3)
		(2.2,3) to [pC, l=$C_3$, *-] (2.2,5) -| (3,5)
		(3,0) to [R,l=$R_5$,-*] (3,1.5)
		to [Tnpn,n=npn1] (3,2.5)
		(npn1.E) node[right=3mm, above=5mm]{$Q_1$}
		(4,0) to [pC, l_=$C_4$, *-] (4, 1.5)--(3,1.5)
		(2.2,0) to [vR, l=$R_3$, *-*] (2.2,2)
		(3,2.5) to node[short]{}(3,3)
		(3,5) to [pR, n=pot1, l_=$R_4$, *-] (3,3)
		(3,5) to [R, l=$R_6$, *-] (5,5)
		to [short,*-o](5,5.5) node[right]{$V_S=40 V$}
		(5,3) to [Tnigfetd,n=mos1] (5,5)
		(mos1.B) node[anchor=west]{$Q_2$}
		(pot1.wiper)  to [R, l=$R_7$] (4.5,4) -| (mos1.G)
		(5,1.5) to [Tpigfetd,n=mos2] (5,2.5)
		(5,0) to (mos2.S)
		(3,2.5) to [R, l=$R_8$, *-] (4.5,2.5)
		-| (mos2.G)
		(mos2.B) node[anchor=west]{$Q_3$}
		(6,3) to [pC, l=$C_5$,-*](5,3)
		(6,3) to [short,-o] (6,2){}
		(mos1.S)--(mos2.D)
		(6,0) to [short,-o] (6,1){} node[above=7mm]{\large{\textbf{SPEAKER}}};
	\end{tikzpicture}
	\caption{电路图}
\end{figure}

\begin{tcolorbox}
	\mybox{Exercise}
	画出$ K_4 $的平面图。
	\begin{figure}[H]
		\centering
		\begin{tikzpicture}
			\node[black, fill=black, circle, inner sep=2pt] at (0,0){};
			\node[black, fill=black, circle, inner sep=2pt] at (2,0){};
			\node[black, fill=black, circle, inner sep=2pt] at (2,2){};
			\node[black, fill=black, circle, inner sep=2pt] at (0,2){};
			\draw[black, thick] (0,0) -- (2,0) -- (2,2) -- (0,2) -- (0,0) -- (2,2);
			\draw[black, thick] (0,2) -- (2,0);
		\end{tikzpicture}
	\end{figure}

	\begin{figure}[H]
		\centering
		\begin{tikzpicture}
			\node[black, fill=black, circle, inner sep=2pt] at (0,0){};
			\node[black, fill=black, circle, inner sep=2pt] at (2,0){};
			\node[black, fill=black, circle, inner sep=2pt] at (2,2){};
			\node[black, fill=black, circle, inner sep=2pt] at (0,2){};
			\draw[black, thick] (0,0) -- (2,0) -- (2,2) -- (0,2) -- (0,0) -- (2,2);
			\draw (0,2) arc [
					start angle=90,
					end angle=340,
					x radius=2.1cm,
					y radius=1.5cm
				] ;
		\end{tikzpicture}
	\end{figure}
\end{tcolorbox}

\begin{tcolorbox}
	\mybox{Exercise}
	画出$ Q_3 $的平面图。
	\begin{figure}[H]
		\centering
		\begin{tikzpicture}
			\node[black, fill=black, circle, inner sep=2pt] at (0,0){};
			\node[black, fill=black, circle, inner sep=2pt] at (2,0){};
			\node[black, fill=black, circle, inner sep=2pt] at (2,2){};
			\node[black, fill=black, circle, inner sep=2pt] at (0,2){};
			\draw[black, thick] (0,0) -- (2,0) -- (2,2) -- (0,2) -- (0,0);

			\node[black, fill=black, circle, inner sep=2pt] at (0.8,0.8){};
			\node[black, fill=black, circle, inner sep=2pt] at (2.8,0.8){};
			\node[black, fill=black, circle, inner sep=2pt] at (2.8,2.8){};
			\node[black, fill=black, circle, inner sep=2pt] at (0.8,2.8){};
			\draw[black, thick] (0.8,0.8) -- (2.8,0.8) -- (2.8,2.8) -- (0.8,2.8) -- (0.8,0.8);

			\draw[black, thick] (0,0) -- (0.8,0.8);
			\draw[black, thick] (0,2) -- (0.8,2.8);
			\draw[black, thick] (2,2) -- (2.8,2.8);
			\draw[black, thick] (2,0) -- (2.8,0.8);
		\end{tikzpicture}
	\end{figure}

	\begin{figure}[H]
		\centering
		\begin{tikzpicture}
			\node[black, fill=black, circle, inner sep=2pt] at (0,0){};
			\node[black, fill=black, circle, inner sep=2pt] at (3,0){};
			\node[black, fill=black, circle, inner sep=2pt] at (3,3){};
			\node[black, fill=black, circle, inner sep=2pt] at (0,3){};

			\node[black, fill=black, circle, inner sep=2pt] at (1,1){};
			\node[black, fill=black, circle, inner sep=2pt] at (1,2){};
			\node[black, fill=black, circle, inner sep=2pt] at (2,2){};
			\node[black, fill=black, circle, inner sep=2pt] at (2,1){};

			\draw[black, thick] (0,0) -- (3,0) -- (3,3) -- (0,3) -- (0,0);
			\draw[black, thick] (1,1) -- (1,2) -- (2,2) -- (2,1) -- (1,1);
			\draw[black, thick] (0,0) -- (1,1);
			\draw[black, thick] (0,3) -- (1,2);
			\draw[black, thick] (3,3) -- (2,2);
			\draw[black, thick] (3,0) -- (2,1);
		\end{tikzpicture}
	\end{figure}
\end{tcolorbox}

一个平面图中的边可以把图分成多个区域（region）。

\begin{tcolorbox}
	\mybox{欧拉公式（Euler's Formula）}\\
	假设G是有e条边和v个顶点的连通平面简单图，平面图的区域数为
	\begin{align}
		r = e - v + 2
	\end{align}
\end{tcolorbox}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\node[black, fill=black, circle, inner sep=2pt] at (0,0){};
		\node[black, fill=black, circle, inner sep=2pt] at (6,0){};
		\node[black, fill=black, circle, inner sep=2pt] at (6,4){};
		\node[black, fill=black, circle, inner sep=2pt] at (0,4){};
		\node[black, fill=black, circle, inner sep=2pt] at (3,0){};
		\node[black, fill=black, circle, inner sep=2pt] at (3,4){};
		\node[black, fill=black, circle, inner sep=2pt] at (6,2){};

		\draw[black, thick] (0,0) -- (6,0) -- (6,4) -- (0,4) -- (0,0);
		\draw[black, thick] (3,4) -- (3,0) -- (0,4);
		\draw[black, thick] (3,4) -- (6,2) -- (3,0);

		\draw (1,1.5) node{$ R_1 $};
		\draw (2,3) node{$ R_2 $};
		\draw (4,2) node{$ R_3 $};
		\draw (5,3.5) node{$ R_4 $};
		\draw (5,0.5) node{$ R_5 $};
		\draw (7,2) node{$ R_6 $};
	\end{tikzpicture}
\end{figure}

\newpage

\section{图着色}

\subsection{图着色（Graph Coloring）}

在为一幅地图着色时，具有共同边界的两个区域通常指定为不同的颜色。简单图的着色就是对每个顶点都指定一种颜色，使得没有两个相邻的顶点颜色相同。着色数（chromatic number）是对一个图着色所使用的最少的颜色数量。

\begin{tcolorbox}
	\mybox{四色定理（The Four Color Theorem）}\\
	平面图的着色数不超过4。
\end{tcolorbox}

\begin{tcolorbox}
	\mybox{Exercise}
	计算着色数。
	\begin{figure}[H]
		\centering
		\begin{tikzpicture}
			\node[black, fill=black, circle, inner sep=2pt] at (0,0){};
			\node[black, fill=black, circle, inner sep=2pt] at (2,2){};
			\node[black, fill=black, circle, inner sep=2pt] at (-1,2){};
			\node[black, fill=black, circle, inner sep=2pt] at (1,4){};
			\node[black, fill=black, circle, inner sep=2pt] at (3,5){};
			\node[black, fill=black, circle, inner sep=2pt] at (-2,5){};

			\draw[black, thick] (0,0) -- (2,2) -- (1,4) -- (-1,2) -- (0,0) -- (1,4);
			\draw[black, thick] (-1,2) -- (2,2) -- (3,5) -- (1,4) -- (-2,5) -- (-1,2);
		\end{tikzpicture}
	\end{figure}

	因为图中包含一个子图$ K_4 $，而$ K_4 $的4个顶点必须要用4种不同的颜色表示，所以图的着色数至少为4。\\
	同时该图可以转换为平面图，根据四色定理，该图的着色数为4。

	\begin{figure}[H]
		\centering
		\begin{tikzpicture}
			\node[blue, fill=blue, circle, inner sep=2pt] at (0,0){};
			\node[black, fill=black, circle, inner sep=2pt] at (2,2){};
			\node[red, fill=red, circle, inner sep=2pt] at (-1,2){};
			\node[orange, fill=orange, circle, inner sep=2pt] at (1,4){};
			\node[blue, fill=blue, circle, inner sep=2pt] at (3,5){};
			\node[blue, fill=blue, circle, inner sep=2pt] at (-2,5){};

			\draw[black, thick] (0,0) -- (2,2) -- (1,4) -- (-1,2) -- (0,0) -- (1,4);
			\draw[black, thick] (-1,2) -- (2,2) -- (3,5) -- (1,4) -- (-2,5) -- (-1,2);
		\end{tikzpicture}
	\end{figure}
\end{tcolorbox}

\newpage